package 题目集.链表;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;
import java.util.StringTokenizer;
//https://pintia.cn/problem-sets/1736590940207706112/exam/problems/1736590972772155403?type=7&page=0
public class 链表去重 {
    public static void main(String[] args) {
        Reader sc=new Reader();
        Map<Integer,Node> map=new HashMap<>();
        boolean[] exist=new boolean[10001];
        int headIndex = sc.nextInt();
        int n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            int addr = sc.nextInt();
            map.put(addr,new Node(addr,sc.nextInt(),sc.nextInt()));
        }
        int currAddr=headIndex;
        Node head = map.get(headIndex);
        Node curr = head;
        while (curr!=null){
            curr.next = map.get(curr.nextAddr);
            curr=curr.next;
        }
        Node h1=new Node();
        Node h2=new Node();
        Node pre1=h1,pre2=h2;
        curr=head;
        while (curr!=null){
            int val = Math.abs(curr.val);
            if (exist[val]){
                pre2.next=curr;
                pre2.nextAddr=curr.addr;
                pre2=curr;
            }else {
                pre1.next=curr;
                pre1.nextAddr=curr.addr;
                pre1=curr;
                exist[val]=true;
            }
            curr=curr.next;
        }
        pre1.next=null;
        pre1.nextAddr=-1;
        pre2.next=null;
        pre2.nextAddr=-1;
        print(h1.next);
        print(h2.next);
    }
    public static void print(Node head){
        while (head!=null){
            System.out.println(head);
            head=head.next;
        }
    }
    static class Node{
        int addr;
        int val;
        int nextAddr;
        Node next;

        public Node() {
        }

        public Node(int addr, int val) {
            this.addr = addr;
            this.val = val;
        }

        public Node(int addr, int val, int nextAddr) {
            this.addr = addr;
            this.val = val;
            this.nextAddr = nextAddr;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Node node = (Node) o;
            return addr == node.addr;
        }

        @Override
        public int hashCode() {
            return Objects.hash(addr);
        }

        @Override
        public String toString() {
            if (nextAddr==-1){
                return String.format("%05d",addr)+" "+val+" "+ -1;
            }else {
                return String.format("%05d",addr)+" "+val+" "+ String.format("%05d",nextAddr);
            }
        }
    }

    static class Reader {
        private BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        private StringTokenizer tokenizer = new StringTokenizer("");

        private String innerNextLine() {
            try {
                return reader.readLine();
            } catch (IOException ex) {
                return null;
            }
        }

        public boolean hasNext() {
            while (!tokenizer.hasMoreTokens()) {    //内存中没有
                String nextLine = innerNextLine();
                if (nextLine == null) {     //且没有下一行
                    return false;
                }
                tokenizer = new StringTokenizer(nextLine);  //读入一行
            }
            return true;
        }

        public String nextLine() {
            tokenizer = new StringTokenizer("");    //清空内存中的字符
            return innerNextLine();
        }

        public String next() {
            hasNext();
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

    }

}

